package 单周赛.history;


import java.util.*;

/**
 * @
 * @date 2024/03/10
 */
public class 第388场单周赛 {

    public static void main(String[] args) {

        //[5,5,5]
        //[2,4,2,7]

        // [4,8,7,5,3,6]
        //[9,2,4,5,4,9]
        System.out.println(minimumBoxes(new int[]{4, 8, 7, 5, 3, 6}, new int[]{9, 2, 4, 5, 4, 9}));

    }

    /**
     * 模拟
     */
    public static int minimumBoxes(int[] apple, int[] capacity) {
        Arrays.sort(capacity);

        int appleSum = 0;
        for (int i : apple) {
            appleSum += i;
        }

        int cSum = 0;
        for (int i = capacity.length - 1; i >= 0; i--) {

            cSum += capacity[i];
            if (cSum >= appleSum) {

                return capacity.length - i;
            }

        }
        return -1;
    }

    /**
     * 优先选择幸福指数大的
     */
    public long maximumHappinessSum(int[] happiness, int k) {
        Arrays.sort(happiness);
        long sum = 0;
        int sub = 0;

        for (int i = happiness.length - 1; i >= 0 && k > 0; i--, k--) {

            sum += Math.max(0, happiness[i] - sub);

            sub++;

        }

        return sum;
    }

    /**
     * 哈希表
     * 每个字符串的子字符串只计算一次，算出全部字符串的子字符串出现的次数
     * 然后将某个字符串出现的子字符串只出现过一次的，排序
     */
    public String[] shortestSubstrings(String[] arr) {
        String[] ans = new String[arr.length];
        Map<String, Integer> map = new HashMap<>();
        for (String str : arr) {

            Set<String> set = new HashSet<>();
            for (int i = 0; i < str.length(); i++) {
                for (int j = i; j < str.length(); j++) {
                    set.add(str.substring(i, j + 1));
                }
            }

            for (String s : set) {
                map.put(s, map.getOrDefault(s, 0) + 1);
            }
        }

        for (int r = 0; r < arr.length; r++) {
            String str = arr[r];
            List<String> list = new ArrayList<>();
            for (int i = 0; i < str.length(); i++) {
                for (int j = i; j < str.length(); j++) {
                    String s = str.substring(i, j + 1);
                    if (map.get(s) == 1) {
                        list.add(s);
                    }
                }
            }
            if (list.size() == 0) {
                ans[r] = "";
                continue;
            }

            list.sort((a, b) -> {
                if (a.length() != b.length()) {
                    return a.length() - b.length();
                } else {
                    return a.compareTo(b);
                }
            });

            ans[r] = list.get(0);
        }
        return ans;
    }

}
